476B - Dreamoon and WiFi - CodeForces Solution


bitmasks brute force combinatorics dp math probabilities *1300

Please click on ads to support us..

Python Code:

def solveExp(index,str_):
    if(index>=len(str_)):
        return 0
    
    if(str_[index]=='+'):
        return 1 + solveExp(index+1,str_)
    else:
        return -1+ solveExp(index+1,str_)

def solveMain(index,str_,target,ans,res,leng):
    if(index>=len(str_)):
        leng.append(True)
        if(ans==target):
            res.append(True)
        
        return 0
    if(str_[index]=='+'):
        solveMain(index+1,str_,target,ans+1,res,leng)
    elif(str_[index]=='-'):
        solveMain(index+1,str_,target,ans-1,res,leng)
    else:
        solveMain(index+1,str_,target,ans+1,res,leng)
        solveMain(index+1,str_,target,ans-1,res,leng)
        
s1=str(input())
s2=str(input())

k1 = solveExp(0,s1)
k2 = []
leng=[]
solveMain(0,s2,k1,0,k2,leng)

if('?' in s2):
    
    op=format(len(k2)/len(leng), '.12f')
    print(op)
else:
    print(len(k2))

C++ Code:


#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	string s1,s2;
	
	cin>>s1>>s2;
	
	int ps1 = 0;
	int ps2 = 0;
	int empty = 0;
	
	for(int i=0; i<s1.size(); i++)
	{
		if(s1[i] == '+')
		{
			ps1++;
		}
		if(s2[i] == '+')
		{
			ps2++;
		}
		if(s2[i] == '?')
		{
			empty++;
		}
	}
	
	int  counter = 0;
	
	
	//cout<<"Empty = "<<empty<<" "<<"LEn = "<<(1<<empty)<<"\n";
	
	for(int i=0; i< (1<<empty); i++)
	{
		//cout<<bitset<32>(i)<<"\n";
		//cout<<__builtin_popcount(i) <<" "<<ps2<<" "<<ps1<<"\n";
		
		if(__builtin_popcount(i) + ps2 == ps1)
		{
			counter++;
		}
	}
	
	cout<<fixed<<setprecision(9)<<(double)counter/(1<<empty)<<endl;

	
	
	return 0;
}


Comments

Submit
0 Comments
More Questions

63A - Sinking Ship
1704B - Luke is a Foodie
298B - Sail
239A - Two Bags of Potatoes
1704E - Count Seconds
682A - Alyona and Numbers
44A - Indian Summer
1133C - Balanced Team
1704A - Two 0-1 Sequences
1467A - Wizard of Orz
1714E - Add Modulo 10
1714A - Everyone Loves to Sleep
764A - Taymyr is calling you
1714B - Remove Prefix
1264F - Beautiful Fibonacci Problem
52A - 123-sequence
1543A - Exciting Bets
1714D - Color with Occurrences
215B - Olympic Medal
1445A - Array Rearrangment
1351A - A+B (Trial Problem)
935B - Fafa and the Gates
1291A - Even But Not Even
1269A - Equation
441A - Valera and Antique Items
1702C - Train and Queries
816B - Karen and Coffee
838D - Airplane Arrangements
148B - Escape
847G - University Classes